import java.util.Objects;

class Person{
    public int id;
    public String name;
    public int age;

    public Person(int id){
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return id == person.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class HashBuckUpgrade<K, V> {
    static class Node<K, V>{
        public K key;
        public V val;
        public Node<K, V> next;

        public Node(K key, V val){
            this.key = key;
            this.val = val;
        }
    }

    private Node<K, V>[] array;
    private int usedSize;

    public HashBuckUpgrade(){
        this.array = new Node[10];
    }

    public void put(K key, V val){
        int hash = key.hashCode();
        int index = hash % this.array.length;

        Node cur = this.array[index];
        while(cur != null){
            if(cur.key.equals(key)){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }

        Node<K, V> node = new Node<>(key, val);
        if(this.array[index] == null){
            this.array[index] = node;
        }else{
            cur = this.array[index];
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
        this.usedSize++;

        double loadFactor = loadFactor();
        if(loadFactor >= 0.75){
            resize();
        }
    }

    private double loadFactor(){
        return this.usedSize * 1.0 / this.array.length;
    }

    private void resize(){
        int size = 2 * this.array.length;
        Node<K, V>[] tmp = new Node[size];

        for(int i = 0; i < this.array.length; i++){
            Node<K, V> cur = this.array[i];

            while(cur != null){
                int hash = cur.key.hashCode();
                int newIndex = hash % tmp.length;

                Node curNext = cur.next;
                if(tmp[newIndex] == null){
                    tmp[newIndex] = cur;
                }else{
                    Node<K, V> t = tmp[newIndex];
                    while(t.next != null){
                        t = t.next;
                    }
                    t.next = cur;
                }
                cur.next = null;
                cur = curNext;
            }
        }
        this.array = tmp;
    }

    public V get(K key){
        int hash = key.hashCode();
        int index = hash % this.array.length;

        Node<K, V> cur = this.array[index];
        while(cur != null){
            if(cur.key.equals(key)){
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}
